package codetop.greedy;

import java.util.Stack;

public class Code402 {
    //1432219 3 1219
    public String removeKdigits(String num, int k) {
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < num.length(); i++) {
            if (stack.isEmpty()) {
                if (num.charAt(i) == 0) continue;
                stack.push(num.charAt(i));
            } else {
                char c = num.charAt(i);
                while (!stack.isEmpty()&&k>0&&c - stack.peek() < 0) {
                    stack.pop();
                    k--;
                }
                if (!stack.isEmpty()||c!='0'){
                    stack.push(c);
                }
            }
        }
        String ans="";
        if (stack.isEmpty()&&k==0)return "0";
        while (!stack.isEmpty()){
            if (k>0) {
                k--;
                stack.pop();
            }
            else {
                ans=stack.pop()+ans;
            }
        }
        return ans.equals("")?"0":ans;
    }
}
